week2手寫作業 戴偉璿

第一題:

note:limxk=k,limx1x=0note:\displaystyle\lim_{x\to \infty}k=k,\displaystyle\lim_{x\to \infty}\cfrac{1}{x}=0

a.\text{a}. limn3n+1n1=limn(3+1n)limn(11n)=31=3\displaystyle\lim_{n\to \infty}\cfrac{3n+1}{n-1}=\cfrac{{\displaystyle\lim_{n\to \infty}(3+\frac{1}{n}})}{{\displaystyle\lim_{n\to \infty}(1-\frac{1}{n}})}=\cfrac{3}{1}=3\\ b.\text{b}. limnnn2+1=limn1limn(n+1n)=1n\displaystyle\lim_{n\to \infty}\cfrac{n}{n^2+1}=\cfrac{{\displaystyle\lim_{n\to \infty}1}}{{\displaystyle\lim_{n\to \infty}(n+\frac{1}{n}})}=\cfrac{1}{n}

note:f(n)O(g(n))note:f(n)\in O(g(n))\Leftrightarrow k>0,N,n>N,f(n)kg(n)\exist k>0,\exist N,\forall n>N,f(n)\le k\cdot g(n)

c.\text{c}. f(n)O(2n)f(n)O(2n+1)f(n)\in O(2^n)\Longleftrightarrow f(n)\in O(2^{n+1})\\ (1).proof  f(n)O(2n)f(n)O(2n+1)(1).proof\;f(n)\in O(2^n)\Longrightarrow f(n)\in O(2^{n+1})\\ f(n)O(2n)\because f(n)\in O(2^n)\\ k0\therefore\exist k\ge 0,limnf(n)2n=k\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}=k\\

limnf(n)2n+1=limnf(n)2n12=k12\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}\cdot\cfrac{1}{2}=k\cdot\cfrac{1}{2},仍為一常數

f(n)O(2n+1)\therefore f(n)\in O(2^{n+1}),成立

(2).proof  f(n)O(2n)f(n)O(2n+1)(2).proof\;f(n)\in O(2^n)\Longleftarrow f(n)\in O(2^{n+1})\\ f(n)O(2n+1)\because f(n)\in O(2^{n+1})\\ k0\therefore\exist k\ge 0,limnf(n)2n+1=l\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}=l\\ limnf(n)2n=limnf(n)2n+12=l2\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^n}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{2^{n+1}}\cdot 2=l\cdot 2,仍為一常數

f(n)O(2n)\therefore f(n)\in O(2^n),成立

(1),(2),(1),(2),得證f(n)O(2n)f(n)O(2n+1)f(n)\in O(2^n)\Longleftrightarrow f(n)\in O(2^{n+1})\\

d.\text{d}. f(n)O(n!)f(n)O((n+1)!)f(n)\in O(n!)\Longleftrightarrow f(n)\in O((n+1)!)\\ (1).proof  f(n)O(n!)f(n)O((n+1)!)(1).proof\;f(n)\in O(n!)\Longrightarrow f(n)\in O((n+1)!)\\ f(n)O(n!)\because f(n)\in O(n!)\\ k0\therefore\exist k\ge 0,limnf(n)n!=k\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=k

limnf(n)(n+1)!=limnf(n)n!1n+1=limnk1n+1=0\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}\cdot\cfrac{1}{n+1}=\displaystyle\lim_{n\to \infty}k\cdot\cfrac{1}{n+1}=0,仍為一常數

f(n)O(n!)\therefore f(n)\in O(n!)\\

(2).proof  f(n)O(n!)f(n)O((n+1)!)(2).proof\;f(n)\in O(n!)\Longleftarrow f(n)\in O((n+1)!)\\ f(n)O((n+1)!)\because f(n)\in O((n+1)!)\\ k0\therefore\exist k\ge 0,limnf(n)(n+1)!=l\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}=l\\ limnf(n)n!=limnf(n)(n+1)!(n+1)=limnl(n+1)=\therefore\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{(n+1)!}\cdot (n+1)=\displaystyle\lim_{n\to \infty}l\cdot (n+1)=\infty,無法收斂成一常數

假設命題成立,設f(n)=(n+1)!f(n)=(n+1)!,則

limnf(n)n!=limn(n+1)!n!=limnn+1=\displaystyle\lim_{n\to \infty}\cfrac{f(n)}{n!}=\displaystyle\lim_{n\to \infty}\cfrac{(n+1)!}{n!}=\displaystyle\lim_{n\to \infty}n+1=\infty

此處產生矛盾,故f(n)O(n!)f(n)O((n+1)!)f(n)\in O(n!)\Longleftarrow f(n)\in O((n+1)!)不成立,故原命題不成立。

f(n)O(n!)\therefore f(n)\in O(n!)

(1),(2),(1),(2),得證f(n)O(n!)f(n)O((n+1)!)f(n)\in O(n!)\Longleftrightarrow f(n)\in O((n+1)!)\\

上次沒證明出來的第四題

題目:序列開始時只包含一個正整數 nn,接著每次對此序列進行如下操作:在序 列中找到任意一個大於 1 的正整數 kk,接著把此數換成任意兩個正整數 a,ba, b,其中a+b=ka + b = k,則此操作得 a×ba × b 分,且數列會多出一項。重複進行以上操作,直到序列中的數均為 1 為止。試證:所有操作的得分總和為n2n2\cfrac{n^2-n}{2}

假設命題成立,

n+1=(i)+(ni+1)n+1=(i)+(n-i+1),此步驟得i(ni+1)=nii2+ii(n-i+1)=ni-i^2+i

ii得分為:i2i2\cfrac{i^2-i}{2}ni+1n-i+1得分為(ni+1)2(ni+1)2\cfrac{(n-i+1)^2-(n-i+1)}{2}

將三步驟的分數相加:nii2+i+i2i2+(ni+1)2(ni+1)2=n2+n2ni-i^2+i+\cfrac{i^2-i}{2}+\cfrac{(n-i+1)^2-(n-i+1)}{2}=\cfrac{n^2+n}{2},成立

故命題成立。